#include "stdafx.h"
#include "CInsertSort.h"
#include "include/tool.h"

#include <gtest/gtest.h>

template <typename T>
void selection_sort(std::vector<T> *A) {
    for (int j = 0; j < A->size() - 1; ++j) {
        int pos = j;
        T min = (*A)[pos];
        for (int i = j; i < A->size(); ++i) {
            if (min > (*A)[i]) {
                min = (*A)[i];
                pos = i;
            }
        }
        if (pos != j) {
            std::swap((*A)[j], (*A)[pos]);
        }
    }
}

CSelectSort::CSelectSort()
{
    //ctor
}

CSelectSort::~CSelectSort()
{
    //dtor
}

int CSelectSort::run(void) {
    int A[] = {31, 41, 59, 26, 41, 58, 33, 78};

    std::cout << "selection sort :";
    std::vector<int> selVector = create_from_array(A, SIZE(A));
    print_vector(selVector);
    selection_sort(&selVector);
    print_vector(selVector);

    return 0;
}

template <typename T>
void insertion_sort(std::vector<T> *A) {
    for (int j = 1; j < A->size(); ++j) {
        T key = (*A)[j];
        int i = j-1;
        while ((i >= 0) && ((*A)[i] > key)) {
            (*A)[i+1] = (*A)[i];
            --i;
        }
        (*A)[i+1] = key;
    }
}

template <typename T>
void insertion_sort_inline_binary_search(std::vector<T> *A) {
    for (int j = 1; j < A->size(); ++j) {
        T key = (*A)[j];
        int low = 0;
        int high = j-1;
        int mid = 0;
        do {
            mid = std::floor((double)(low + high)/2);
            if (key == (*A)[mid]) {
                break;
            } else if (key < (*A)[mid]) {
                high = mid-1;
            } else {
                low = mid+1;
            }
        } while (low <= high);

        if (key > (*A)[mid]) {
            ++mid;
        }
        for (int i = j-1; i >= mid; --i) {
            (*A)[i+1] = (*A)[i];
        }
        (*A)[mid] = key;
    }
}

template <typename T>
void insertion_sort_recursion(std::vector<T> *A, int r) {
    if (r > 0) {
        insertion_sort_recursion(A, r-1);
        T key = (*A)[r];
        for (int i = 0; i <= r-1; ++i) {
            if (key < (*A)[i]) {
                for (int j = r-1; j >= i; --j) {
                    (*A)[j+1] = (*A)[j];
                }
                (*A)[i] = key;
                return;
            }
        }
    }
}



CInsertSort::CInsertSort()
{
    //ctor
}

CInsertSort::~CInsertSort()
{
    //dtor
}

int CInsertSort::run(void) {
    int A[] = {31, 41, 59, 26, 41, 58, 33, 78};

    std::cout << "insertion sort :";
    std::vector<int> insertVector = create_from_array(A, SIZE(A));
    print_vector(insertVector);
    insertion_sort(&insertVector);
    print_vector(insertVector);

    std::cout << "insertion sort inline binary search :";
    std::vector<int> insertBinaryVector = create_from_array(A, SIZE(A));
    print_vector(insertBinaryVector);
    insertion_sort_inline_binary_search(&insertBinaryVector);
    print_vector(insertBinaryVector);

    std::cout << "recursion insertion sort :";
    std::vector<int> insertRecursionVector = create_from_array(A, SIZE(A));
    print_vector(insertRecursionVector);
    insertion_sort_recursion(&insertRecursionVector, insertRecursionVector.size()-1);
    print_vector(insertRecursionVector);

    return 0;
}

TEST(CInsertSort, run)
{
	CInsertSort().run();
}